package offer.tree;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @author DengYuan2
 * @create 2021-03-03 19:34
 */
public class n_M_236 {
    public static void main(String[] args) {

    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null || root==p || root==q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left==null){
            return right;
        }
        if (right==null){
            return left;
        }
        return root;
    }

    /**
     * 存储公共节点
     * @param root
     * @param p
     * @param q
     * @return
     */

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null){
            return null;
        }
        HashMap<Integer,TreeNode> map =  new HashMap<Integer,TreeNode>();
        ArrayList<Integer> list = new ArrayList<>();
        while (p!=null){
            list.add(p.val);
            p=map.get(p.val);
        }
        while (q!=null){
            if (list.contains(q.val)){
                return q;
            }
            q=map.get(q.val);
        }
        return null;
    }

    public void getParent(TreeNode node,HashMap<Integer,TreeNode> map){
        if (node==null){
            return;
        }
        if (node.left!=null){
            map.put(node.left.val,node);
            getParent(node.left,map);
        }
        if (node.right!=null){
            map.put(node.right.val,node);
            getParent(node.right,map);
        }
    }
}
